Intersection of Two Arrays II

LeetCode 350 | Difficulty: Easy

Easy

Problem Description

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order.

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]
Explanation: [9,4] is also accepted.

Constraints:

- `1 <= nums1.length, nums2.length <= 1000`

- `0 <= nums1[i], nums2[i] <= 1000`

Follow up:

- What if the given array is already sorted? How would you optimize your algorithm?

- What if `nums1`'s size is small compared to `nums2`'s size? Which algorithm is better?

- What if elements of `nums2` are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

Topics: Array, Hash Table, Two Pointers, Binary Search, Sorting

---

Approach

Two Pointers

Use two pointers to traverse the array, reducing the search space at each step. This avoids the need for nested loops, bringing complexity from O(n²) to O(n) or O(n log n) if sorting is involved.

When to use

Array is sorted or can be sorted, and you need to find pairs/triplets that satisfy a condition.

Binary Search

Binary search reduces the search space by half at each step. The key insight is identifying the monotonic property — what condition lets you decide to go left or right?

When to use

Sorted array, or searching for a value in a monotonic function/space.

Hash Map

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

---

Solutions

Solution 1: C# (Best: 300 ms)

Metric	Value
Runtime	300 ms
Memory	N/A
Date	2018-04-17

Solution

public class Solution {
    public int[] Intersect(int[] nums1, int[] nums2) {
            Dictionary<int, int> oc = new Dictionary<int, int>();
    List<int> result = new List<int>();
    for (int i = 0; i < nums1.Length; i++)
    {
        if (oc.ContainsKey(nums1[i]))
            oc[nums1[i]]++;
            else
            oc.Add(nums1[i],1);
    }

    for (int i = 0; i < nums2.Length; i++)
    {
        if (oc.ContainsKey(nums2[i]) && oc[nums2[i]] > 0)
        {
            result.Add(nums2[i]);
            oc[nums2[i]]--;

        }
    }
    return result.ToArray();
    }
}

---

Complexity Analysis

Approach	Time	Space
Two Pointers	$O(n)$	$O(1)$
Binary Search	$O(log n)$	$O(1)$
Sort + Process	$O(n log n)$	$O(1) to O(n)$
Hash Map	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.
• Ask: "Can I sort the array?" — Sorting often enables two-pointer techniques.
• Hash map gives O(1) lookup — think about what to use as key vs value.
• Precisely define what the left and right boundaries represent, and the loop invariant.